package stu.day49;

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 邻接表：图中每个节点对应的出边列表
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : times) {
            graph.computeIfAbsent(edge[0], x -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});
        }

        // 最短距离数组，初始化为无穷大，起点 k 的距离设为 0
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        // 优先队列，存放 [当前距离, 节点]，按照当前距离升序排序
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], node = cur[1];
            if (d > dist[node]) continue;

            if (graph.containsKey(node)) {
                for (int[] edge : graph.get(node)) {
                    int nextNode = edge[0], weight = edge[1];
                    if (d + weight < dist[nextNode]) {
                        dist[nextNode] = d + weight;
                        pq.offer(new int[]{dist[nextNode], nextNode});
                    }
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxTime = Math.max(maxTime, dist[i]);
        }
        return maxTime;
    }
}

